package chapter03;
import chapter02.MyUtil;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class boat1 {

    static int n;

    public static void main(String[] args) {
        File file=new File("C:\\Users\\levovo\\Desktop\\算法实验2\\boat1.txt");
        Scanner sc= null;
        try {
            sc = new Scanner(file);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        n=sc.nextInt();
        //System.out.println(n);
        int[][] rents=new int[n+1][n+1];
        int[][] best=new int[n+1][n+1];
        int[][] ways=new int[n+1][n+1];
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++) {
                rents[i][j]=sc.nextInt();
                best[i][j]=rents[i][j];
                //System.out.print(rents[i][j]+" ");
            }
            //System.out.println(" ");
        }
        rent(best, ways);
        System.out.println("花费最少租金为："+best[1][n]);
        System.out.print("最优路径为：1");
        path(1, n, ways);
        System.out.println();
        sc.close();

    }

    //计算最少租金
    public static void rent(int[][] best, int[][] way) {
        //Integer i=1;
        System.gc();
        int j;
        for(int d=3;d<=n;d++) {
            for(int i=1;i<=n-d+1;i++) { //子问题的初始点
                j=i+d-1; //终点站点
                for(int k=i+1;k<j;k++) { //可以停靠的点
                    int temp=best[i][k]+best[k][j]; //在站点处停靠
                    if(temp<best[i][j]) { //停留后的租金小于直达的租金
                        best[i][j]=temp;
                        way[i][j]=k; //记录停靠点
                    }
                }
            }
        }
    }

    //最优路径存储
    public static void path(int i,int j,int[][] way) {
        if(way[i][j]==0) {
            System.out.print("-->"+j);
            return;
        }
        path(i, way[i][j], way);
        path(way[i][j], j, way);
    }
}
